package q287_findDuplicate;

public class Solution_2 {
    /*
    我们以1 3 4 2 2为例
    假设有一个数组cnt[i]存放对于i这个数 数组中<=i的数的个数
    那么在这个数组中情况就是这样的 1 3 4 5 也就是
    小于等于1的数的个数为1个 小于等于2的数的个数为3个 小于等于3的数的个数为4个 小于等于4的数的个数为5个
    而重复的数是2 所以可以发现如果有一个数重复 那么就会出现cnt[i] > i
    我们只需要用二分法找出来最小的这个cnt[i] > i的i就可以了
     */
    public int findDuplicate(int[] nums) {
        int n = nums.length;
        int l = 1, r = n - 1, ans = -1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            int cnt = 0;
            for (int num : nums) {
                if (num <= mid) cnt++;
            }
            if (cnt <= mid) {
                l = mid + 1;
            } else {
                r = mid - 1;
                ans = mid;
            }
        }
        return ans;
    }

}
